#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=5e5+100;
typedef long long LL;
const LL INF=1e10;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL lst[maxn],nxt[maxn],a[maxn];
vector<LL>v[2*maxn];
struct Tree{
    LL l,r,val;
}tree[maxn*4];
void push_up(LL p){
    tree[p].val=min(tree[p*2].val,tree[p*2+1].val);
}
void build(LL p,LL l,LL r){
    tree[p].l=l;tree[p].r=r;tree[p].val=INF;
    if(l==r){tree[p].val=nxt[l];return;}
    LL mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);
}
void modify(LL p,LL l,LL r,LL d){
    if(l<=tree[p].l&&r>=tree[p].r){
        tree[p].val=d;
        return;
    }
    LL mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) modify(p*2,l,r,d);
    if(r>mid) modify(p*2+1,l,r,d);
    push_up(p);
}
LL query(LL p,LL l,LL r){
    if(l<=tree[p].l&&r>=tree[p].r){
        return tree[p].val;
    }
    LL ans=INF;
    LL mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) ans=min(ans,query(p*2,l,r));
    if(r>mid)  ans=min(ans,query(p*2+1,l,r));
    return ans;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n,q;cin>>n>>q;

  for(LL i=1;i<=n;i++) cin>>a[i];
  for(LL i=1;i<=1e6;i++) v[i].push_back(0);
  for(LL i=1;i<=n;i++){
    v[a[i]].push_back(i);
  }
  for(LL i=1;i<=1e6;i++) v[i].push_back(INF);

  for(LL i=1;i<=1e6;i++){
    for(LL j=1;j<v[i].size()-1;j++){
        lst[v[i][j]]=v[i][j-1];
        nxt[v[i][j]]=v[i][j+1];
    }
  }
  build(1,1,n);
  while(q--){
    LL x,l,r;cin>>x;
    if(x==1){
        cin>>l;
        modify(1,l,l,INF);
        modify(1,lst[l],lst[l],nxt[l]);
        nxt[lst[l]]=nxt[l];

        if(nxt[l]<INF){
            lst[nxt[l]]=lst[l];
        }
        lst[l]=0;
        nxt[l]=INF;
    }
    else if(x==2){
        cin>>l>>r;
        LL t=query(1,l,r);
        if(t<=r){
            cout<<"1"<<"\n";
        }
        else cout<<"0"<<"\n";
    }
  }
return 0;
}
